package Prefix_and;

import java.util.HashMap;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-01-25
 * Time:22:34
 * Text：和可被 K 整除的子数组
 * 重点，dp[i]:存储0-n-1之间和%k的余数。利用同余道理
 * 余数(a%p+p)%p
 */
public class Text6 {
    /**
      * 重点，dp[i]:存储0-n-1之间和%k的余数。利用同余道理
      * 余数(a%p+p)%p
    */
    public int subarraysDivByK(int[] nums, int k) {
        HashMap<Integer,Integer> map1=new HashMap<>();
        map1.put(0%k,1);
        int num=0,ret=0;
        for(int i=0;i<nums.length;i++){
            num+=nums[i];
            int r=(num%k + k) % k;
            ret+=map1.getOrDefault(r,0);
            map1.put(r,(map1.getOrDefault(r,0)+1));
        }
        return ret;
    }
}
